import common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 437. path-sum-iii 路径和III
 * https://leetcode-cn.com/problems/path-sum-iii/
 */
class PathSumIII {
    /**
     *      方法： 使用哈希表和递归来计算路径和
     *
     *      Args:
     *          root: Optional[TreeNode] - 二叉树的根节点
     *          targetSum: int - 目标路径和
     *
     *      Returns:
     *          int: 满足目标路径和的路径数量
     *
     *      Time: O(n) - 其中n是二叉树的节点数，每个节点只被访问一次
     *
     *      Space: O(n) - 其中n是二叉树的节点数，用于存储哈希表和递归调用栈
     */
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> cnt = new HashMap<>();
        cnt.put(0L, 1);
        return dfs(root, 0,  targetSum, cnt);
    }

    private int dfs(TreeNode node, long s, int targetSum, Map<Long, Integer> cnt){
        if (node == null){
            return 0;
        }
        s += node.val;
        int ans = cnt.getOrDefault(s - targetSum, 0); //cnt[s]++
        cnt.merge(s, 1, Integer::sum);
        ans += dfs(node.left, s, targetSum, cnt);
        ans += dfs(node.right, s, targetSum, cnt);
        cnt.merge(s, -1, Integer::sum); // //cnt[s]--
        return ans;

    }
}